/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Redistribution;

import Graph.*;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author oliviersputael
 */
public class Redistribution {
	public Redistribution(Graph G1, Graph G2, List<Color> colors, double a, double b, double ps, double p, int k) {
		alpha = a;
		beta = b;
		psi = ps;
		this.p = p;
		this.k = k;
		this.colors = colors;
		newGraph = new Graph(G1); // This is done to avoid creating another copy (see in constructCompGraph)
		compareGraph1 = constructCompGraph(G1);
		newGraph = new Graph(G2);
		compareGraph2 = constructCompGraph(G2);
		MCS = new Graph();
		recolorationGraph = new Graph();
		bestAssignation = new ArrayList<Node>();
		//compare();
		//coloration();
	}
	
	public Graph getFirstCompareGraph () {
		return compareGraph1;
	}
	
	public Graph getSecondCompareGraph () {
		return compareGraph2;
	}
	
	public Graph getMCS () {
		return MCS;
	}
	
	public Graph getNewGraph () {
		return newGraph;
	}
	
	public void doComparison () {
		compare();
		newGraph.colorGraph(MCS);
	}
	
	public void doColoration () {
		coloration();
	}
	
	/*
	 * Private methods
	 */
	
	private Graph constructCompGraph (Graph G) {
		Graph compGraph = new Graph(G);
		
		for (Node node : newGraph.getNodes()) {
			if (node.isConstrained()) {
				compGraph.removeNodeFromGraph(node);
			}
		}
		
		return compGraph;
	}
	
	private void constructRecolorationGraph () {
		for (Node n : newGraph.getNodes()) {
			if (!n.getInstruction().isAtomic())  {
				recolorationGraph.addNodeToGraph(n); 
				if (n.getInstruction().getNext() != null) {
					for (Instructions instr : n.getInstruction().getNext()) {
						Node nextNode = newGraph.getNodeFromInstruction(instr);
						if (!recolorationGraph.isAnEdge(n, nextNode)) {
							double weight = 0;
							// IF link : link between condition of IF and its first instruction
							String thisLabel = n.getInstruction().getLabel();
							String nextLabel = nextNode.getInstruction().getLabel();
							String thisPosit = n.getInstruction().getPosition();
							String nextPosit = nextNode.getInstruction().getPosition();
							int endPosThis = thisPosit.length();
							int endPosNext = nextPosit.length();
							
							if (thisLabel.substring(0, 2).equals("IF")) {
								if (nextPosit.equals(thisLabel))
									weight = p - (psi / 2);
								else if (nextPosit.substring(endPosNext - 4, endPosNext).equals("ELSE") &&
										 nextPosit.substring(0, endPosNext - 4).equals(thisLabel.substring(0, endPosNext - 4)))
									weight = (1 - p) - (psi / 2);
								else if (!nextPosit.substring(0, endPosNext - 4).equals(thisLabel))
									weight = psi;
							}
							else if (thisPosit.substring(0, 2).equals("IF")) {
								if (nextPosit.equals(thisPosit))
									weight = 1;
								else
									weight = 1;
							}
							else if (thisLabel.substring(0, 5).equals("WHILE")) {
								if (nextPosit.equals(thisLabel))
									weight = k;
								else
									weight = 1;
							}
							else if (thisPosit.substring(0, 5).equals("WHILE")) {
								if (nextLabel.substring(0, 5).equals("WHILE"))
									weight = k;
								else if (nextPosit.equals(thisPosit))
									weight = 1;
							}
							else if (thisPosit.equals(nextPosit)) {
								weight = 1;
							}

							// Inheritance : searching for previous edge
							boolean found = false;
							for (int i = 0; i < recolorationGraph.getNumberOfEdges() && !found; i++) {
								//if (!thisPosit.equals(nextPosit)) { // Changing context, inherit of weight
									if (recolorationGraph.getEdgesFromID(i).contains(n) && 
										recolorationGraph.getEdgesFromID(i).getOtherNode(n).getInstruction().getNext().contains(n.getInstruction())) {
										weight = weight * recolorationGraph.getEdgesFromID(i).getWeight();
										found = true;
									}
								//}
							}

							recolorationGraph.addEdgeToGraph(new Edges(n, nextNode, weight));
						}
					}
				}
			}
		}
	}

	private void compare() {
		List<NodesCouple> candidates = new ArrayList<NodesCouple>();
		List<NodesCouple> old_candidates = new ArrayList<NodesCouple>();
		List<NodesCouple> matching = new ArrayList<NodesCouple>();
		NodesCouple temp = new NodesCouple();
		
		for (Node n1 : compareGraph1.getNodes()) {
			for (Node n2 : compareGraph2.getNodes()) {
				candidates.add(new NodesCouple(n1, n2));
			}
		}
		
		while (!candidates.isEmpty() && !candidates.equals(old_candidates)) {
			boolean stop = false;
			for (int i = 0; i < candidates.size() && !stop; i++) {
				NodesCouple pair = candidates.get(i);
				if (pair.getFirstNode().equals(pair.getSecondNode())) {
					matching.add(pair);
					stop = true;
					temp.setFirstNode(pair.getFirstNode());
					temp.setSecondNode(pair.getSecondNode());
				}
			}
			
			old_candidates = new ArrayList<NodesCouple>(candidates);
			candidates.clear();
			
			for (Node n1 : compareGraph1.getNodes()) {
				for (Node n2 : compareGraph2.getNodes()) {
					if (compareGraph1.isAnEdge(n1, temp.getFirstNode()) && compareGraph2.isAnEdge(n2, temp.getSecondNode())) {
						boolean found = false;
						for (int i = 0; i < matching.size() && !found; i++) {
							found = matching.get(i).contains(n1) || matching.get(i).contains(n2);
						}
						
						if (!found) {
							// The pair can be a candidate
							candidates.add(new NodesCouple(n1, n2));
						}
					}
				}
			}
			
			if (candidates.isEmpty()) {
				for (Node n1 : compareGraph1.getNodes()) {
					for (Node n2 : compareGraph2.getNodes()) {
						boolean found = false;
						for (int i = 0; i < matching.size() && !found; i++) {
							NodesCouple matched = matching.get(i);
							found = (matched.contains(n1) || matched.contains(n2));
						}
						
						if (!found) {
							// The pair can be a candidate
							candidates.add(new NodesCouple(n1, n2));
						}
					}
				}
			}
		}
		
		for (NodesCouple pair : matching) {
			pair.getSecondNode().setColor(pair.getFirstNode().getColor());
			MCS.addNodeToGraph(pair.getSecondNode());
		}
		MCS.generateEdges();
	}
	
	private void coloration () {
		constructRecolorationGraph();
		
		List<Node> oldColoration = new ArrayList<Node>();
		for (Node n : recolorationGraph.getNodes()) {
			oldColoration.add(new Node(n));
			// Re-init every nodes to White
			n.setColor(newGraph.getColorFromConstraintNb(-1));
		}
		
		minCostValue = Double.MAX_VALUE;
		recolor(oldColoration, 0);
		
		System.out.print("\n");
		System.out.println("bestAssignation : ");
		for (Node n : bestAssignation) {
			System.out.print(n.getColor().getName().substring(0, 1));
		}
		System.out.print(" - Cost : " + minCostValue + "\n");
		
		for (Node n : newGraph.getNodes()) {
			for (Node no : bestAssignation) {
				if (n.equals(no))
					n.setColor(no.getColor());
			}
		}
	}
	
	private void recolor (List<Node> oldNodes, int indexN) {
		if (indexN == recolorationGraph.getNumberOfNodes()) {
			double currentValue = computeCost(oldNodes);
			if (currentValue < minCostValue && isFeasible()) {
				minCostValue = currentValue;
				bestAssignation = new ArrayList<Node>();
				for (Node n : recolorationGraph.getNodes()) 
					bestAssignation.add(new Node(n));
			}
		}
		else {
			for (int m = 0; m < colors.size(); m++) {
				// Not considering the last color: White
				Color c = colors.get(m);
				recolorationGraph.getNodeFromID(indexN).setColor(c);
				if (c.getConstraintNb() > -1) {
					// Not considering the White color here	
					if (indexN > 0) {
						// No need to compute a cost if only one color is assigned
						if (computeCost(oldNodes) < minCostValue) {
							// If the partial value computed is >= than the minValue, it's no use to continue
							indexN++;
							recolor(oldNodes, indexN);
							indexN--;
						}
					}
					else {
						indexN++;
						recolor(oldNodes, indexN);
						indexN--;
					}
				}
			}
		}
	}
	
	private double computeCost(List<Node> oldNodes) {
		double result = 0;
		
		for (int i = 0; i < recolorationGraph.getNumberOfNodes(); i++) {
			Node n = recolorationGraph.getNodeFromID(i);
			String colorName = n.getColor().getName();
			if (n.isColored()) {
				if (oldNodes.get(i).isColored() && !oldNodes.get(i).getColor().getName().equals(colorName)) {
					// We changed the color
					result = result + alpha * 1;
				}
				
				List<Edges> nodeEdges = new ArrayList<Edges>(recolorationGraph.getUniqueEdgesFromNode(n));
				for (Edges e : nodeEdges) {
					if (e.getOtherNode(n).isColored() &&
						!e.getOtherNode(n).getColor().getName().equals(colorName))
						result = result + beta * e.getWeight();
				}
			}
		}
		
		return result;
	}
	
	private boolean isFeasible () {
		boolean result = true;
		
		for (int i = 0; i < recolorationGraph.getNumberOfNodes() && result; i++) {
			Node n = recolorationGraph.getNodeFromID(i);
			if (n.isConstrained()) {
				Color c = newGraph.getColorFromConstraintNb(n.getConstraint());
				result = result && n.getColor().equals(c);
			}
			if (result) {
				// Now, we check if the current node has to have the same color as another one
				List<Edges> nodeEdges = new ArrayList<Edges>(newGraph.getUniqueEdgesFromNode(n));
				for (int j = 0; j < nodeEdges.size(); j++) {
					Color c = nodeEdges.get(j).getOtherNode(n).getColor();
					result = result && n.getColor().equals(c);
				}
			}
		}
		
		return result;
	}
	
	Graph newGraph;
	Graph compareGraph1;
	Graph compareGraph2;
	Graph MCS;
	Graph recolorationGraph;
	List<Color> colors;
	List<Node> bestAssignation;
	double minCostValue;
	double alpha;
	double beta;
	double psi;
	double p;
	int k;
}
